package com.leaves.leetcode.array.t15_3Sum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;




/**
 * 核心要点：
 * 1、排序加双指针
 * 2、为了不选到重复的数字对，考虑对原数组进行排列
 * 3、对于a+b+c=0若固定了a，b和c就是一增一降的关系，对于这种关系可以考虑双指针
 * 5、针对第4点，左右指针肯定都是要遍历到left==right的位置的，一种是外层遍历left内层遍历right，一种是外层只遍历left和right关系，left和right的遍历放在内层。这两种都行，第一种逻辑比较清晰
 */
class Solution {

    /**
     * 排序加双指针
     * 1、为了不挑选到相同位置的数，使用3层for循环
     * 2、为了不选到重复的数字对，考虑对原数组进行排列
     * 3、对于a+b+c=0若固定了a，b和c就是一增一降的关系，对于这种关系可以考虑双指针
     * 4、双指针不一定就要左右同时移动，可以像该官方的方式，先外层遍历左指针，跳过重复的元素，在内存遍历右指针(这里对于右指针的遍历，跳过不符合公式的方式更优于跳过重复元素，因为可能有一连串不符合公式的数字串但并不重复，这样可以一次性过滤掉，无需再次进入外层循环)
     * 5、针对第4点，左右指针肯定都是要遍历到left==right的位置的，一种是外层遍历left内层遍历right，一种是外层只遍历left和right关系，left和right的遍历放在内层。这两种都行，第一种逻辑比较清晰
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(nlogn) 排序空间
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSumOfficial(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int n = nums.length;
        Arrays.sort(nums);

        for (int first = 0; first < n - 2; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) continue;
            int third = n - 1;
            int target = -nums[first];
            for (int second = first + 1; second < n; ++second) {
                if (second > first+1 && nums[second] == nums[second - 1]) continue;
                while (second < third && nums[second] + nums[third] > target) third--;
                if (second == third) break;
                if (nums[second] + nums[third] == target) {
                    res.add(Arrays.asList(nums[first], nums[second], nums[third]));
                }
            }
        }
        return res;
    }

    /**
     * 自己写的，思路同官方的一致，但是执行时间上略慢，慢的主要原因在于注释的那块
     * 被注释的那块，由于r是跳过重复元素，而非跳过一系列不符合要求的右侧第三个数字，所以会导致多次进入外层的while和sum > 0的if判断，这无疑多了不少的操作，
     * 比如右侧的数字串 3 4 4 5 5 6 6 7 7 这里从4开始就不符合要求了，但注释的内容在4 5、5 6、6 7 上会跳回外层的while再进入sum > 0的if块，继续判断，不如直接过滤掉不符合要求的数字(> 0的直接去掉)
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(nlogn) 排序空间
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int l = i + 1, r = nums.length - 1;
            int target = -nums[i];

            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                }
                if (sum == 0 || sum > 0) {
//                    while (l < r && nums[r] == nums[r-1]) r--;
//                    r--;
                    while (l < r && nums[l] + nums[r] > target) r--;
                }
                if (sum == 0 || sum < 0) {
                    while (l < r && nums[l] == nums[l+1]) l++;
                    l++;
                }
            }
        }
        return res;
    }

}